package lc.q150_200;

import lc.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class BSTIterator {

    private int idx;
    private final List<Integer> arr = new ArrayList<>();

    public BSTIterator(TreeNode root) {
        // 中序遍历将数据存到数组中
        this.idx = 0;
        buildIndex(root);
    }

    private void buildIndex(TreeNode root) {
        if (root == null) {
            return;
        }
        buildIndex(root.left);
        arr.add(root.val);
        buildIndex(root.right);
    }

    public int next() {
        // 向左遍历
        return arr.get(idx ++);
    }

    public boolean hasNext() {
        return arr.size() > idx;
    }
}
